package JanChallenges;

import BasicDataStructures.TreeNode;
import Utils.TreeUtils;

public class Day11_P1026 {
    public static void main(String[] args) {
        Day11_P1026 q = new Day11_P1026();
        String data = "1#2###0######3";
        TreeNode root = TreeUtils.generateTree(data);
        TreeUtils.printTree(root, "pre", true);
        TreeUtils.printTree(root, "pre", false);

        TreeUtils.printTree(root, "in", true);
        TreeUtils.printTree(root, "in", false);

        TreeUtils.printTree(root, "pos", true);
        TreeUtils.printTree(root, "pos", false);

        System.out.println(q.maxAncestorDiff(root));
    }

    int maxDiff = Integer.MIN_VALUE;
    int upperLimit = (int) (1e5 + 1);
    int lowerLimit = -1;

    public int maxAncestorDiff(TreeNode root) {
        posProcess(root);

        return maxDiff;
    }

    //maxDiff = |a.val - b.val|
    //|node.val - lmin|, |node.val - lmax|
    //|node.val - rmin|, |node.val - rmax|
    //node.val, lmin, lmax, node.val, rmin, rmax
    public int[] posProcess(TreeNode node) {
        if (node == null) {
            return new int[]{lowerLimit, upperLimit};
        }
        int[] l = posProcess(node.left);
        int[] r = posProcess(node.right);
        int curMin = node.val;
        int curMax = node.val;
        if (l[0] != lowerLimit) {
            maxDiff = Math.max(maxDiff, node.val - l[0]);
            curMin = Math.min(curMin, l[0]);
        }
        if (l[1] != upperLimit) {
            maxDiff = Math.max(maxDiff, l[1] - node.val);
            curMax = Math.max(curMax, l[1]);
        }

        if (r[0] != lowerLimit) {
            maxDiff = Math.max(maxDiff, node.val - r[0]);
            curMin = Math.min(curMin, r[0]);
        }
        if (r[1] != upperLimit) {
            maxDiff = Math.max(maxDiff, r[1] - node.val);
            curMax = Math.max(curMax, r[1]);
        }
        return new int[] {curMin, curMax};
    }
}
